/*!
 * \file Graph.h
 * \brief A data structure representing a Simple Graph.
 *
 * \see Graphs
 *
 * \date Jun 18, 2012
 * \author correa
 */

#ifndef WGRAPH_H_
#define WGRAPH_H_

#include <cstdio>
#include <math.h>
#include "OrderedSet.h"
#include "OrderedBinaryRelation.h"
#include "BitTools.h"
#include "Graph.h"
#include "Graphs.h"

/*!*
 * \class Weight
 *
 * \brief This class represents the weights in a weighted graph.
 *
 * The objects of this class represents the weights in a weight graph.
 * The weights can be given to vertexes and/or edges.
 *
 * This class also implements a unitary weight for all graph as pattern.
 *
 * \tparam the type of the weight.
 * */
template <class W=int>
class Weight {

public:
	/*!
	 * \brief The simple constructor
	 *
	 * Create an object of this class that represent a unitary weight
	 * over a graph.
	 */
	virtual ~Weight() {};

	/*!
	 * \brief The weight associate to a specified vertex.
	 *
	 * Retrieve the weight associate to a specified vertex, if the vertex is not
	 * in the graph an error will occur.
	 *
	 * \param i the specified vertex
	 *
	 * \return the weight associate to the specified vertex
	 */
	virtual W weight(long i);

	/*!
	 * \brief The weight associate to a specified edge.
	 *
	 * Retrieve the weight associate to a specified edge, if the edge is not
	 * in the graph an error will occur.
	 *
	 * \param i the first endpoint of the specified edge
	 *
	 * \param j the second endpoint of the specified edge
	 *
	 * \return the weight associate to the specified edge
	 */
	virtual W weight(long i, long j);

	/*!
	 * \brief Retrieve the weights of a set of vertexes
	 *
	 * \param begin the first vertex
	 *
	 * \param end the last vertex
	 *
	 * \return a array that contains the weight of the vertexes
	 * in the interval [begin, end]
	 */
	virtual W* toarray(long begin, long end);

	/*!
	 * \brief Retrieve the weights of a set of edges
	 *
	 * \param rbegin the first vertex
	 *
	 * \param rend the last vertex
	 *
	 * \param cbegin the first in each edge
	 *
	 * \param cend the last in each edge
	 *
	 * \return a array that contains the weight of the edges
	 * having the first endpoint in the interval [rbegin, rend]
	 * and the second in the interval [cbegin, cend]
	 */
	virtual W**	toarray(long rbegin, long cbegin, long rend, long cend);
};

template <>
inline int Weight<int>::weight(long i) {
	return 1;
}

template <>
inline int Weight<int>::weight(long i, long j) {
	return 1;
}

template <>
inline long Weight<long>::weight(long i) {
	return 1;
}

template <>
inline long Weight<long>::weight(long i, long j) {
	return 1;
}

template <>
inline double Weight<double>::weight(long i) {
	return 1.0;
}

template <>
inline double Weight<double>::weight(long i, long j) {
	return 1.0;
}

template <class W>
inline W* Weight<W>::toarray(long begin, long end) {
	return NULL;
}

template <class W>
inline W** Weight<W>::toarray(long rbegin, long cbegin, long rend, long cend) {
	return NULL;
}

/*!
 * \class WGraphs
 *
 * \brief Represents a collection of algorithms for weighted graphs.
 */
template<typename W , class T>
class WGraphs{
public:

	/*!
	 * \brief
	 *
	 * \param g
	 *
	 * \param w
	 *
	 * \param cover
	 *
	 * \param factory
	 *
	 * \param R
	 *
	 * \param r
	 *
	 * \return
	 */
	static long greedyCoverSort(Graph<T>* g, Weight<W>* w, long** cover, OrderedSetFactory<long>* factory, long* R, long r);

	/*!
	 * \brief
	 *
	 * \param g
	 *
	 * \param w
	 *
	 * \param cover
	 *
	 * \param factory
	 *
	 * \param R
	 *
	 * \param r
	 *
	 * \return
	 */
	static long dsaturCoverSort(Graph<T>* g, Weight<W>* w, long** cover, OrderedSetFactory<long>* factory, long* R, long r);

	/*!
	 * \brief
	 *
	 * \param g
	 *
	 * \param w
	 *
	 * \param cover
	 *
	 * \param factory
	 *
	 * \return
	 */
	static long mcrCoverSort(Graph<T>* g, Weight<W>* w, long** cover, OrderedSetFactory<long>* factory);

	/*!
	 * \brief
	 *
	 * \param g
	 *
	 * \param w
	 *
	 * \param cover
	 *
	 * \param factory
	 *
	 * \param R
	 *
	 * \param r
	 *
	 * \param Ro
	 *
	 * \return
	 */
	static long greedySort(Graph<T>* g, Weight<W>* w, long** cover, OrderedSetFactory<long>* factory, long* R, long r, long** Ro);

	/*!
	 * \brief
	 *
	 * \param g
	 *
	 * \param w
	 *
	 * \param cover
	 *
	 * \param factory
	 *
	 * \param R
	 *
	 * \param r
	 *
	 * \param Ro
	 *
	 * \return
	 */
	static long dsaturSort(Graph<T>* g, Weight<W>* w, long** cover, OrderedSetFactory<long>* factory, long* R, long r, long** Ro);

	/*!
	 * \brief
	 *
	 * \param g
	 *
	 * \param w
	 *
	 * \param cover
	 *
	 * \param factory
	 *
	 * \param R
	 *
	 * \param r
	 *
	 * \param Ro
	 *
	 * \return
	 */
	static long mcrSort(Graph<T>* g, Weight<W>* w, long** cover, OrderedSetFactory<long>* factory, long* R, long r, long** Ro);

	/*!
	 * \brief
	 *
	 * \param g
	 *
	 * \param w
	 *
	 * \param R
	 *
	 * \param r
	 *
	 * \return
	 */
	static long readDimacsGraph(Graph<T>* g, Weight<W>* w, FILE * graphFile, graphType t, OrderedSetFactory<long>* factory);

};

template<typename W, class T>
long WGraphs<W,T>::greedyCoverSort(Graph<T>* g, Weight<W>* w, long** cover, OrderedSetFactory<long>* factory, long* R, long r){
	//TODO
	return 0;
}

template<typename W, class T>
long WGraphs<W,T>::dsaturCoverSort(Graph<T>* g, Weight<W>* w, long** cover, OrderedSetFactory<long>* factory, long* R, long r){
	//TODO
	return 0;
}

template<typename W, class T>
long WGraphs<W,T>::mcrCoverSort(Graph<T>* g, Weight<W>* w, long** cover, OrderedSetFactory<long>* factory){
	//TODO
	return 0;
}

template<typename W, class T>
long WGraphs<W,T>::greedySort(Graph<T>* g, Weight<W>* w, long** cover, OrderedSetFactory<long>* factory, long* R, long r, long** Ro){
	//TODO
	return 0;
}

template<typename W, class T>
long WGraphs<W,T>::dsaturSort(Graph<T>* g, Weight<W>* w, long** cover, OrderedSetFactory<long>* factory, long* R, long r, long** Ro){
	//TODO
	return 0;
}

template<typename W, class T>
long WGraphs<W,T>::mcrSort(Graph<T>* g, Weight<W>* w, long** cover, OrderedSetFactory<long>* factory, long* R, long r, long** Ro){
	//TODO
	return 0;
}

template<typename W, class T>
long WGraphs<W,T>::readDimacsGraph(Graph<T>* g, Weight<W>* w, FILE * graphFile, graphType t, OrderedSetFactory<long>* factory){
	//TODO
	return 0;
}

#endif /* WGRAPH_H_ */
